package Point.Double.Util;

import org.junit.Test;

/**
 *
 * [找边界]
 * 最后的if 难理解
 *  * 因为 for 中间没有return
 *
 *  1） left == nums.length
 *      2 3 4 找1
 *
 *  2） nums[left] != target
 *      -> 没找到，死在中间了（ 1 1 3 4 找2 ）
 *
 */
public class 二分_找边界 {
    /**
     * 1 2 2 2 3
     * 0 1 2 3 4
     */
    public int findLeftEdge(int[] nums, int target) {
        // l r --绑定--> [] = +-1
        int left = 0, right = nums.length - 1;
        while (left <= right) { // right=n 时 就是 w <
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                right = mid - 1; // 1 2 2 2 3 找最左的2【唯一特殊处】
            }
        }
        // 左过头 / 右过头 ｜ 没找到，死在中间了（ 1 1 3 4 找2 ） -> 因为 for 中间没有return
        if (left == nums.length || nums[left] != target) { // * 这里||有一个满足，就不会进入后面的[n],不会越界
            return -1;
        }
        return left; // 可不是-1
    }

    public int findRightEdge(int[] nums, int target) {
        // l r -> [] = +-1
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                left = mid + 1;// *
            }// 千万不要开始回头写代码，把下面架写完！
        }
        // -1 n ｜ tar
        if (right == -1 || nums[right] != target)
            return -1;
        return right;
    }

    @Test
    public void test() {
        int[] nums = new int[]{1, 2, 2, 2, 3};
        System.out.println("左ind：" + findLeftEdge(nums, 2));
        System.out.println("右ind：" + findRightEdge(nums, 2));
    }
}
